q = []
res = []
s = [([],[1],2)]

seq = '1234'

q.append(s)

while len(q):
    path = q.pop()
    out,stack,_next = path[-1]
    if len(out)==4:
        res.append(path)
        continue

    # push
    if _next < 5:
        q.append(path + [(out,stack+[_next],_next+1)])
    # pop
    if len(stack):
        q.append(path+[ (out+[stack[-1]], stack[:-1],_next) ] )

possible = set( ''.join(seq[i-1] for i in path[-1][0]) for path in res )

from itertools import permutations

not_possible = set( ''.join(i) for i in permutations(seq) ) - possible

print('%d possible solutions:'%len(possible))
print(*possible,sep=',')

print('%d not possible permutations:'%len(not_possible))
print(*not_possible,sep=',')

print('possible paths:')
for path in res:
    for out,stack,_ in path:
        x = ''.join(seq[i-1] for i in out)
        y = ''.join(seq[i-1] for i in stack)
        print( x+' '*(4-len(x))+'['+y+' '*(4-len(y))+']->',end='')
    print()